package com.leetcode;

import ds.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No144
 * @description 144. 二叉树的前序遍历
 * @date 2021/3/11 上午11:41
 */
public class No144 {
    public static void main(String[] args) {

        /**
         *                1
         *               / \
         *              2   3
         *                 /
         *                5
         */
        TreeNode root = new TreeNode(1);
        TreeNode t1 = new TreeNode(2);
        TreeNode t2 = new TreeNode(3);
        TreeNode t3 = new TreeNode(5);
        root.left = t1;
        root.right = t2;
        t2.left = t3;
        List<Integer> res1 = preorderTraversal(root);
        print(res1);
        List<Integer> res2 = preorderTraversal2(root);
        print(res2);

    }

    // 方法一 递归
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        subPreorder(root,res);
        return res;
    }

    private static void subPreorder(TreeNode root, List<Integer> res) {
        if(root == null){
            return;
        }
        res.add(root.val);
        subPreorder(root.left,res);
        subPreorder(root.right,res);

    }


    // 方法二 非递归
    public static List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        // 使用LinkedList模拟栈
        if(root == null){
            return res;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        while (!stack.isEmpty()){
            TreeNode t = stack.removeLast();
            res.add(t.val);
            if(t.right != null){
                stack.addLast(t.right);
            }
            if(t.left != null){
                stack.addLast(t.left);
            }
        }
        return res;
    }

    public static void print(List<Integer> res){
        int size = res.size();
        for (int i = 0; i < size ; i++) {
            System.out.print(res.get(i));
            if(i != size - 1){
                System.out.print("-");
            }

        }
        System.out.println();
    }

}
